Non-volatile data storage devices, such as universal serial bus (USB) flash memory devices or removable storage cards, have allowed for increased portability of data and software applications. Flash memory devices can enhance data storage density by storing multiple bits in each flash memory cell. For example, Multi-Level Cell (MLC) flash memory devices provide increased storage density by storing 2 bits per cell, 3 bits per cell, 4 bits per cell, or more. Although increasing the number of bits per cell and reducing device feature dimensions may increase the storage density of a memory device, a bit error rate of data stored at the memory device may also increase.
Error correction coding (ECC) is often used to correct errors that occur in data read from a memory device. Prior to storage, data may be encoded by an ECC encoder to generate redundant information (e.g. “parity bits”) that may be stored with the data as an ECC codeword. Conventionally, encoding data to generate an ECC codeword, such as a quasi-cyclic low-density parity-check (QC-LDPC) codeword, includes multiplying the data with a generator matrix. A systematic QC-LDPC generator matrix includes a parity portion composed of circulant matrices. Because each row of a circulant matrix is a cyclically shifted version of the previous row of the circulant matrix, QC-LDPC encoding may be simplified using a shift-register type encoder architecture. However, due to a relatively high density of non-zero entries in irregular locations in the parity portion of a QC-LDPC generator matrix, QC-LDPC encoders conventionally include a dedicated multiplier circuit for each column of the parity portion for multiplying a message symbol with the generator matrix in order to reduce encoding latency.
To reduce the number of multipliers used in a QC-LDPC encoder, a Fourier transform of the generator matrix over a finite field may be used. Because the Fourier transform of a circulant matrix is a diagonal matrix, non-zero entries are only located along the matrix diagonal and a reduced number of multipliers may be used, with one dedicated multiplier for each block column of circulant matrices in the parity portion of the generator matrix for multiplying a message symbol with the generator matrix. However, multiplying an input message (e.g., data to be encoded) with the Fourier transform of the generator matrix results in an output codeword with symbols that are elements of the finite field corresponding to the transformed generator matrix (e.g., Galois field GF(26)), rather than of the input message (e.g., a “binary” message with symbols that are elements of GF(2)).
In order to obtain a binary codeword using a Fourier transform of the generator matrix of a QC-LDPC code, additional processing has been previously proposed that is applied to the input message and to the transformed generator matrix. However, the proposed additional processing includes performing permutations of rows and columns of the transformed generator matrix and also processing the input message by linearly combining together elements that appear in different “blocks” of the input message (i.e., sections of the input message that correspond to different circulant matrices in the generator matrix) to generate a mapped message. In addition, a reverse permutation of the product of the mapped message and the permuted transformed generator matrix is required to obtain a codeword. The multiple permutations add additional complexity and latency of encoding, and the message mapping across multiple “blocks” further increases latency and storage requirements because large portions or all of the input message have to be received and stored before message mapping can be completed. Another drawback of the previously proposed encoding process is that it is limited to binary LDPC codes and is not applicable to non-binary LDPC codes.